

//给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 
//
// 你可以按 任何顺序 返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4, k = 2
//输出：
//[
//  [2,4],
//  [3,4],
//  [2,3],
//  [1,2],
//  [1,3],
//  [1,4],
//] 
//
// 示例 2： 
//
// 
//输入：n = 1, k = 1
//输出：[[1]] 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 20 
// 1 <= k <= n 
// 
// Related Topics 数组 回溯 
// 👍 924 👎 0


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 77.组合.combinations
 *
 * @author orz
 * @since 2022-03-30 22:31:49
 **/

class Solution_77 {
    public static void main(String[] args) {
        Solution solution = new Solution_77().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        private List<List<Integer>> result = new ArrayList<>();
        private LinkedList<Integer> track = new LinkedList<>();

        public List<List<Integer>> combine(int n, int k) {
            backtrack(1, n, k);
            return result;
        }

        private void backtrack(int start, int n, int k) {
            if (track.size() == k) {
                result.add(new LinkedList<>(track));
                return;
            }

            for (int i = start; i <= n; i++) {
                track.addLast(i);
                backtrack(i + 1, n, k);
                track.removeLast();
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}